package Aleehot100;

/**
 * ClassName: c090
 * Package: Aleehot100
 * Description:32. 最长有效括号
 * 这个有点难，多搞几遍理解理解
 * @Author BCXJ
 * @Create 2025/9/13 19:37
 * @Version 1.0
 * @Since 1.0
 */
public class c090 {
    public static void main(String[] args) {
        String str = "())(())";
        System.out.println(longestValidParentheses(str));
    }

  

    public static int longestValidParentheses(String s) {
        int n = s.length();
        char[] charArray = s.toCharArray();
        if(n < 2) {
            return 0;
        }

        int maxLen = 0;
        // dp数组
        int[] dp = new int[n]; // dp[i]: 以s[i]结尾的最长有效括号长度
        for (int i = 1; i < n; i++) {
            if(charArray[i] == ')') {
                // 情况1："...()"
                if(charArray[i - 1] == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else {
                    // 情况2："...))"
                    int prevLen = dp[i - 1];
                    int matchPos = i - prevLen - 1;
                    if(matchPos >= 0 && s.charAt(matchPos) == '(') {
                        dp[i] = dp[i - 1] + 2;
                        if(matchPos - 1 >= 0) {
                            dp[i] += dp[matchPos - 1];
                        }
                    }
                }
                maxLen = Math.max(maxLen, dp[i]);
            }

        }

        return maxLen;
    }

}
